package leetcode_1001_1100;

import java.util.*;

public class LeeCode_1048 {
    public static void main(String[] args) {
        System.out.println(longestStrChain2(new String[]{"a", "b", "ba", "bca", "bda", "bdca"}));
    }
    private static int longestStrChain2(String[] words) {
        Arrays.sort(words, (Comparator.comparingInt(String::length)));
        Map<String, Integer> map = new HashMap<>();
        int ans = 1;
        for (String word : words) {
            int max = 1;
            for (int i = 0; i < word.length(); i++) {
                String newW = word.substring(0, i) + word.substring(i + 1);
                if (map.containsKey(newW)) {
                    ans = Math.max(map.get(newW) + 1, ans);
                    max = Math.max(map.get(newW) + 1, max);
                }
            }
            map.put(word, max);
        }
        return ans;
    }
    private static int longestStrChain(String[] words) {
        Set<String> set = new HashSet<>(Arrays.asList(words));
        int[] ans = new int[1];
        Arrays.sort(words, (o1, o2) -> o2.length() - o1.length());
        for (String word : words) {
            dfs(set, word, 1, ans, new HashSet<>());
        }
        return ans[0];
    }
    private static void dfs(Set<String> set,String word, int i, int[] ans, Set<String> used){
        if (used.contains(word))
            return;
        used.add(word);
        int len = word.length();
        for (int j = 0; j < len; j++) {
            String newW = word.substring(0, j) + word.substring(j + 1, len);
            if (set.contains(newW)){
                dfs(set, newW, i + 1, ans, used);
            }else {
                ans[0] = Math.max(ans[0], i);
            }
        }
    }
}
